5  Lezione 6,7 - 09/10, 10/10

• La prima idea per calcolare la similarità tra vettori è quella di utilizzare la distanza euclidea. Scartiamo subito questa prima idea perchè la distanza euclidea è molto grande con vettori di lunghezze diverse. Se prendo un documento e lo “raddoppio”, confrontando l’originale e quello raddoppiato avranno una similarità diversa da 0 con questo modello, ovvero non sono identificati come lo stesso vettore
  • La soluzione consiste nel considerare gli angoli tra i vettori piuttosto che la distanza euclidea
• Cosine similarity: tecnica euristica per misurare la similarità tra due vettori calcolando il coseno dell’angolo tra loro compreso.
  • Applichiamo quindi una euristica sulla lunghezza dei vettori utilizzando la norma due: ||x|| = \sqrt{\sum_{i} x_{i}^2}
    • Dividere un vettore per la sua norma due lo rende di lunghezza unitaria (versore).
  • Formula di similarità normalizzata del coseno: cos(\vec{q}, \vec{d}) = \dfrac{\vec{q} \cdot \vec{d}}{|\vec{q}| |\vec{d}|} = \dfrac{\sum_{i = 1}^{|V|} q_i d_i}{\sqrt{\sum_{i = 1}^{|V|} q_i^2} \sqrt{\sum_{i = 1}^{|V|} d_i^2}}
  • Formula di similarità con vettori normalizzali o che non si vogliono normalizzare si riduce al prodotto scalare: cos(\vec{q}, \vec{d}) = \vec{q} \cdot \vec{d} = \sum_{i = 1}^{|V|} q_i d_i
  • La similarità del coseno può assumere valori nell’intervallo [0, 1], infatti:
    • Se i vettori sono già normalizzati la loro lunghezza è unitaria, pertanto al denominatore ci sarà il prodotto tra due vettori unitari (quindi 1), per cui sarà sufficiente calcolare solo il numeratore;
    • Se il vettore query ed il vettore documento non hanno termini in comune, il numeratore si annulla, ottenendo cos(\vec{q}, \vec{d}) = 0. In effetti il coseno di due vettori è nullo quanto essi sono perpendicolari, ovvero alla massima distanza angolare.
• Un modo di indicare quali schemi sono stati utilizzati per la pesatura della query e quali per la pesatura del documento consiste nell’utilizzo della smart notation, cioè una notazione del tipo ddd.qqq in cui, in ogni tripla, ogni carattere corrisponde all’iniziale dello schema di pesatura rispettivamente per il Term Frequency, il Document Frequency e la Normalizzazione, e i primi tre caratteri si riferiscono al documento, gli altri tre alla query.

Esempio

Calcoliamo la cosine similarity tra 3 documenti

Sia data la seguente tabella:

\begin{pmatrix}Termini & Doc1 & Doc2 & Doc3 \\ affection & 115 & 58 & 20 \\ jealous & 10 & 7 & 11 \\ gossip & 2 & 0 & 6 \\ wuthering & 0 & 0 & 38\end{pmatrix}

Calcolo la log frequency weighting:

affection in Doc1 = 1 + log(115) = 3.06

jealous in Doc1 = 1 + log(10) = 2

e così via

\begin{pmatrix}Termini & Doc1 & Doc2 & Doc3 \\ affection & 3.06 & 2.76 & 2.30 \\ jealous & 2.00 & 1.85 & 2.04 \\ gossip & 1.30 & 0 & 1.78 \\ wuthering & 0 & 0 & 2.58 \end{pmatrix}

Normalizzo la lunghezza dei vettori:

affection in Doc1 = \dfrac{3.06}{\sqrt{3.06^2 + 2^2 + 1.3^2}} = 0.789

e così via

\begin{pmatrix}Termini & Doc1 & Doc2 & Doc3 \\ affection & 0.789 & 0.832 & 0.524 \\ jealous & 0.515 & 0.555 & 0.465 \\ gossip & 0.335 & 0 & 0.405 \\ wuthering & 0 & 0 & 0.588 \end{pmatrix}

Sono pronto a calcolare la cosine similarity:

cos(Doc1, Doc2) = 0.789 \cdot 0.832 + 0.515 \cdot 0.555 + 0.335 \cdot 0.0 + 0.0 \cdot 0.0 = 0.94

e così via

5.1 WordNet

• Wordnet è un’ontologia linguistica top-level, ovvero fornisce una conoscenza generica e non specifica di un determinato dominio.
• Ispirandosi alla memoria lessicale umana, l’organizzazione del lessico si suddivide in nomi, verbi, aggettivi e avverbi.
• Una parola è un’associazione fra una word form ed una word meaning, dove per word form si intende l’espressione fisica della parola, ovvero la stringa che la descrive, per word meaning si intende il significato sottinteso (lessicale) della parola.
  • A tutti gli effetti Wordnet realizza il mapping tra word form e word meaning, che potremmo rappresentare con una matrice
• Una word form è polisemica se ad essa possono essere associate più word meaning.
• Due word form sono sinonimi se ad esse è associata la stessa word meaning.
• Ogni word meaning è rappresentata dall’insieme delle word form che possono essere usate per esprimerla, ovvero un synset (synonym set)
  • Ad esempio, data la word meaning a small racket with a long handle used for playing squash, il suo synset è costituito da squash racket, squash racquet, bat
  • Un synset associato ad una word form consente all’utente di inferire la semantica della word form in esame purché conosca la semantica di almeno una word form elencata nel synset.
  • Quando si effettua la ricerca di una parola, Wordnet restituisce tutti i sinonimi, ordinati in maniera decrescente per rilevanza, con relativa glossa ed eventuale frase esemplificativa.
• L’elenco dei significati di una parola è definito come sense inventory
  • Ogni significato è memorizzato mediante un codice, che funge da chiave primaria nel dizionario di WordNet
• I significati dei synset (NON le parole) sono collegati attraverso diversi tipi di relazioni chiaramente definite. Definiamo le relazioni che regolano i legami dei sostantivi
  • Relazione is_a: considerando Wordnet come un albero di synset, esso può quindi svilupparsi verso l’alto per iperonimia (generalizzazione), da “gatto” si passa a “felino”, oppure verso il basso, iponimia (specializzazione), da “roditore” si passa a “topo”.
  • Relazione part-of: questa relazione può collegare una parte con il tutto, in questo caso si parla di meronimia, oppure il tutto con una parte, in questo caso si parla di olonimia. Ad esempio, “ala” è un meronimo di “pipistrello”, in quanto l’ala è una parte del pipistrello, mentre “pipistrello” è un olonimo di “ala” in quanto un pipistrello è costituito dall’ala.
  • In base all’albero di generalizzazione si può capire quanto vicino sia un concetto alla parola cercata (misura di similarità semantica), utilizzando ad esempio la Leacock Chodorow Similarity: il path più breve è dato dal numero di archi tra il concetto di partenza e quello di destinazione passando per il least common ancestor, mentre il path massimo è dato dal doppio della profondità dell’albero, il tutto smussato e normalizzato utilizzando la funzione logaritmo

Esempio

The white cat is hunting the mouse

Scegliamo cat da disambiguare e mouse come termine di contesto.

Siano N il numero di nodi del percorso da cat a mouse, e D la massima profondità della tassonomia. Consideriamo D = 16

SINSIM(cat, mouse) = -\log\left(\dfrac{N}{2D}\right) = -\log\left(\dfrac{5}{32}\right) = 0.806

Risultato: cat e mouse sono abbastanza vicini

flowchart LR
Mammal --> Carnivore
Mammal --> Rodent
Carnivore --> Feline
Rodent --> Mouse
Feline --> Cat

Domande tipiche

1. Come è organizzata la conoscenza in WordNet?

Bozza di risposta: Parole divise come nella memoria lessicale dell’uomo, matrice con word form e word meaning, polisemia, sinonimia, …

2. Come sono organizzate le relazioni in WordNet?

Bozza di risposta: Parlare in generale di WordNet, andare nello specifico nelle relazioni